#include <vector>
#include <queue>
#include <stack>
#include <utility>
#include <iostream>

//spots[i][j] == false means point(i,j) can't be passed
//bfs
//assume spots[0][0] must be true
//a[i][j] store the parent, used for construct the path from (0,0) to (X,Y)
void find_path_bfs(std::vector<std::vector<std::pair<int,int> > >& a,const std::vector<std::vector<bool> >& spots){
	const int X = a.size()-1;
	const int Y = a[0].size()-1;
	std::pair<int,int> unvisited(-1,-1);
	std::queue<std::pair<int,int> > q;
	q.push(std::make_pair(0,0));
	while(!q.empty()){
		std::pair<int,int> curr = q.front();
		q.pop();
		if (curr.first < X && spots[curr.first+1][curr.second] && a[curr.first+1][curr.second] == unvisited){
			q.push(std::make_pair(curr.first+1,curr.second));
			a[curr.first+1][curr.second] = curr;
		}
		if (curr.second < Y && spots[curr.first][curr.second+1] && a[curr.first][curr.second+1] == unvisited){
			q.push(std::make_pair(curr.first,curr.second+1));
			a[curr.first][curr.second+1] = curr;
		}
	}
}

void find_path_dfs(std::vector<std::vector<std::pair<int,int> > >& a, const std::vector<std::vector<bool> >& spots){
	const int X = a.size()-1;
	const int Y = a[0].size()-1;
	std::pair<int,int> unvisited(-1,-1);
	std::stack<std::pair<int,int> > q;
	q.push(std::make_pair(0,0));
	while(!q.empty()){
		std::pair<int,int> curr = q.top();
		q.pop();
		if (curr.second < Y && spots[curr.first][curr.second+1] && a[curr.first][curr.second+1] == unvisited){
			q.push(std::make_pair(curr.first,curr.second+1));
			a[curr.first][curr.second+1] = curr;
		}
		if (curr.first < X && spots[curr.first+1][curr.second] && a[curr.first+1][curr.second] == unvisited){
			q.push(std::make_pair(curr.first+1,curr.second));
			a[curr.first+1][curr.second] = curr;
		}
	}
}

bool construct_path(std::vector<std::vector<std::pair<int,int> > >& a, int i, int j){
	if(i==0 && j==0) {
		std::cout << "(0,0)";
		return true;
	}
	std::pair<int,int> parent = a[i][j];
	if(parent.first < 0 ||parent.second < 0)
		return false;
	bool r = construct_path(a,a[i][j].first,a[i][j].second);
	std::cout << " -> (" << i << "," << j << ")" ;
	return r;
}

//return true if there is a path from (i,j) to goal(X,Y)
bool find_path_recursive(int i, int j, std::stack<std::pair<int,int> >&path, const std::vector<std::vector<bool> >& spots, 
						 std::vector<std::vector<bool> >& visited){
	const int X = spots.size()-1;
	const int Y = spots[0].size()-1;
	bool res = false;
	if (i==X && j==Y) {
		path.push(std::make_pair(i,j));
		return true;
	}
	if (i<X && spots[i+1][j] && !visited[i+1][j]) { 
		visited[i+1][j] = true;
		res = find_path_recursive(i+1,j,path,spots, visited) ;
	}
	if (!res && j<Y && spots[i][j+1] && !visited[i][j+1] ){
		visited[i][j+1] = true;
		res = find_path_recursive(i, j+1, path, spots, visited) ;
	}
	if (res)
		path.push(std::make_pair(i,j));
	return res;
}
void construct_candidates(int i, int j, std::vector<std::pair<int,int> >& c, const std::vector<std::vector<bool> >&spots)
{
	const int X = spots.size()-1;
	const int Y = spots[0].size()-1;
	if ( i < X && spots[i+1][j] ) 
		c.push_back(std::make_pair(i+1,j));
	if ( j < Y && spots[i][j+1] )
		c.push_back(std::make_pair(i,j+1));	
}

void process_path(const std::vector<std::pair<int,int> >&path){
	for (int i = 0; i < path.size(); ++i) {
		std::cout << "(" << path[i].first << "," << path[i].second << ")";
		if(i != path.size() -1)
			std::cout << " -> ";
	}
	std::cout << std::endl;
}

void find_all_path_backtrack(int i, int j, std::vector<std::pair<int,int> >&path, const std::vector<std::vector<bool> >&spots)
{
	const int X = spots.size()-1;
	const int Y = spots[0].size()-1;
	std::vector<std::pair<int,int> > c;
	if ( i == X && j == Y ) {
		path.push_back(std::make_pair(i,j));
		process_path(path);
		path.pop_back();
	}
	else {
		construct_candidates(i,j,c,spots);
		for (int k = 0; k < c.size(); ++k) {
			path.push_back(std::make_pair(i,j));
			find_all_path_backtrack(c[k].first, c[k].second, path, spots);
			path.pop_back();
		}
	}
		
}

void find_all_path_backtrack_1(int i, int j, std::vector<std::pair<int,int> >&path, const std::vector<std::vector<bool> >&spots)
{
	const int X = spots.size()-1;
	const int Y = spots[0].size()-1;
	std::vector<std::pair<int,int> > c;
	if ( i == X && j == Y ) {
		path[i+j] = std::make_pair(i,j);
		process_path(path);
	}
	else {
		construct_candidates(i,j,c,spots);
		for (int k = 0; k < c.size(); ++k) {
			path[i+j] = std::make_pair(i,j);
			find_all_path_backtrack_1(c[k].first, c[k].second, path, spots);
		}
	}
		
}

//return true if there is a path from (0,0) to (i,j)
bool find_path_recursive_from_goal(int i, int j, std::stack<std::pair<int,int> >&path, const std::vector<std::vector<bool> >& spots, 
						 const std::vector<std::vector<bool> >& visited){
							 return true;
}


 void construct_path(std::stack<std::pair<int,int> >&path) {
	 while(!path.empty()){
		 std::pair<int,int> curr = path.top();
		 path.pop();
		 std::cout << "(" << curr.first << "," << curr.second << ")";
		 if(!path.empty())
			 std::cout << " -> ";
	 }
	 std::cout << std::endl;
 }


void init(std::vector<std::vector<std::pair<int,int> > >& a, std::vector<std::vector<bool> >& spots, std::vector<std::vector<bool> >& visited){
	const int X = 3;
	const int Y = 4;
	bool spots_arr[X+1][Y+1] = { 
		{1, 1, 1, 1, 1},
		{1, 0, 0, 0 ,1},
		{1, 0, 1, 1, 1},
		{1, 1, 1, 1, 1}
	};
	std::pair<int,int> unvisited(-1,-1);
	a.resize(X+1);
	spots.resize(X+1);
	visited.resize(X+1);
	for (int i = 0; i <=X; ++i){
		a[i].resize(Y+1);
		spots[i].resize(Y+1);
		visited[i].resize(Y+1);
		for (int j = 0; j <=Y; ++j){
			a[i][j] = unvisited;
			spots[i][j] = spots_arr[i][j];
			visited[i][j] = false;
		}
	}
}

void test_9_2(){
	
	std::vector<std::vector<std::pair<int,int> > > a;
	std::vector<std::vector<bool> > spots;
	std::vector<std::vector<bool> > visited;

	std::cout << " **** find a path ****\n";
	init(a, spots, visited);
	find_path_bfs(a,spots);
	bool res = construct_path(a,a.size()-1,a[0].size()-1); std::cout << std::endl;
	std::cout << (res? "there is a path" : "there is no path") << std::endl;

	init(a, spots, visited);
	find_path_dfs(a,spots);
	res = construct_path(a,a.size()-1,a[0].size()-1); std::cout << std::endl;
	std::cout << (res? "there is a path" : "there is no path") << std::endl;

	init(a, spots, visited);
	std::stack<std::pair<int,int> > path;
	res = find_path_recursive(0,0,path,spots,visited);
	construct_path(path);
	std::cout << (res? "there is a path" : "there is no path") << std::endl;

	std::cout << " **** find all paths ****\n";
	std::vector<std::pair<int,int> > path_all(spots.size() + spots[0].size() -1);
	init(a, spots, visited);
	find_all_path_backtrack_1(0,0,path_all,spots);
}
